package 学习计划.数据结构;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/majority-element/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=cqjfoh6
 */
public class _169_多数元素 {

    /**
     * 执行用时：2 ms，内存消耗：44.8MB
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int len = n >> 1;
        Arrays.sort(nums);
        return nums[len];
    }

    /**
     * 执行用时：15 ms，内存消耗：46.9MB
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums) {
        int n = nums.length;
        int len = n >> 1;
        int res = 0;
        Map<Integer, Integer> cache = getMap(nums);
        for (Map.Entry<Integer, Integer> entry : cache.entrySet()) {
            if (entry.getValue() > len) {
                res = entry.getKey();
                break;
            }
        }
        return res;
    }

    private Map<Integer, Integer> getMap(int[] nums) {
        Map<Integer, Integer> cache = new HashMap<>();
        for (int num : nums) {
            if (!cache.containsKey(num)) {
                cache.put(num, 1);
            } else {
                cache.put(num, cache.get(num) + 1);
            }
        }
        return cache;
    }

    /**
     * 执行用时：2 ms，内存消耗：45.2MB
     * @param nums
     * @return
     */
    public int majorityElement3(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += num == candidate ? 1 : -1;
        }

        return candidate;
    }
}

